package 算法模板;

import java.util.Arrays;

/**
 * 计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。
 * 它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），
 * 快于任何比较排序算法。 [1]  当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))
 * 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)),
 * 如归并排序，堆排序）
 * <p>
 * 来源：百度百科
 */
public class 计数排序 {

    public static void main(String[] args) {

        //排序的数组
        int[] nums = {
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 9,
                5100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 92, 95};

        int[] r1 = countSort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(r1));
        System.out.println("------------------");

        efficientCountSort(nums);
        System.out.println(Arrays.toString(nums));

        System.out.println("得出结果是否一致：" + Arrays.deepEquals(new int[][]{r1}, new int[][]{nums}));

    }

    /**
     * 不改变原来的数组
     *
     * @param a
     * @return
     */
    public static int[] countSort(int[] a) {
        long l = System.currentTimeMillis();
        int b[] = new int[a.length];
        int max = a[0], min = a[0];
        for (int i : a) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }//这里k的大小是要排序的数组中，元素大小的极值差+1
        int k = max - min + 1;
        int c[] = new int[k];
        for (int i = 0; i < a.length; ++i) {
            c[a[i] - min] += 1;//优化过的地方，减小了数组c的大小
        }
        for (int i = 1; i < c.length; ++i) {
            c[i] = c[i] + c[i - 1];
        }
        for (int i = a.length - 1; i >= 0; --i) {
            b[--c[a[i] - min]] = a[i];//按存取的方式取出c的元素
        }
        long l1 = System.currentTimeMillis();
        System.out.println("第一种方式耗时：" + (l1 - l));
        return b;
    }

    /**
     * 直接在原来的数组上进行排序，不需要额外的空间
     *
     * @param nums
     * @return
     */
    public static int[] efficientCountSort(int[] nums) {
        long l = System.currentTimeMillis();
        //先找出最大值和最小值，初始化好排序用的数组
        int max = nums[0], min = nums[0];
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        //1,2,3     3-1=2，显然需要+1，才能一定将数组中的元素装进去
        int[] sortNums = new int[max - min + 1];
        //排序，原数组元素值-最小元素=在排序数组索引的位置
        //1-1-->0，2-1-->1，3-1-->2
        for (int i = 0; i < nums.length; i++) {
            sortNums[nums[i] - min]++;
        }
        int cur = 0; //将排序好的数组元素组装进原数组
        for (int i = 0; i < sortNums.length; i++) {
            if (sortNums[i] != 0) {
                while (sortNums[i]-- > 0) {
                    nums[cur++] = i + min;
                }
            }
        }
        long l1 = System.currentTimeMillis();
        System.out.println("第二种方式耗时：" + (l1 - l));
        return nums;
    }

}
